package LeetCode;

import java.util.*;

public class LC_406_QueueReconstructionbyHeight {

    public static void main(String[] args) {

    }

    public class Solution {
        private void swap(int[][] people, int a, int b) {
            int t1 = people[a][0], t2 = people[a][1];
            people[a][0] = people[b][0];
            people[a][1] = people[b][1];
            people[b][0] = t1;
            people[b][1] = t2;
        }

        public int[][] reconstructQueue(int[][] people) {
            int n = people.length;
            for (int i = 0; i < n; i++) {
                for (int j = i + 1; j < n; j++) {
                    if (people[i][0] < people[j][0])
                        swap(people, i, j);
                    else if (people[i][0] == people[j][0] && people[i][1] > people[j][1])
                        swap(people, i, j);
                }
            }
            //按照顺序插入
            List<Integer> la = new ArrayList<>();
            List<Integer> lb = new ArrayList<>();
            for (int[] aPeople : people) {
                la.add(aPeople[1], aPeople[0]);
                lb.add(aPeople[1], aPeople[1]);
            }
            for (int i = 0; i < n; i++) {
                people[i][0] = la.get(i);
                people[i][1] = lb.get(i);
            }
            return people;
        }

    }

    public class Solution_2 {
        public int[][] reconstructQueue(int[][] people) {
            int size = people.length;
            LinkedList<int[]> list = new LinkedList<>();
            for (int[] aPeople : people)
                list.add(new int[]{aPeople[0], aPeople[1], 0});
            int ans[][] = new int[size][];
            for (int i = 0; i < size; i++) {
                list.sort((a, b) -> {
                    if (a[1] == b[1])
                        return a[0] - b[0];
                    return a[1] - b[1];
                });
                int[] head = list.removeFirst();
                ans[i] = new int[]{head[0], head[1] + head[2]};
                for (int[] p : list) {
                    if (p[0] <= head[0]) {
                        p[1] -= 1;
                        p[2] += 1;
                    }
                }
            }
            return ans;
        }

    }
}